package 中等.搜索.深度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 * <p>
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1
 * 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0
 * （代表水）包围着。
 * <p>
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 * <p>
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/max-area-of-island
 */
public class 岛屿的最大面积_695 {

    public static void main(String[] args) {

    }

    /**
     * 深度优先搜索+栈
     *
     * @param grid
     * @return
     */
    public static int DFSmaxAreaOfIsland(int[][] grid) {
        //面积
        int area = 0;
        //定义四个方向
        int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int rows = grid.length;
        int columns = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                //遍历找到一个岛屿
                if (grid[i][j] == 1) {
                    int curArea = 0;
                    //搜索这个岛屿相邻的岛屿个数
                    Deque<int[]> stack = new ArrayDeque<>();
                    stack.addFirst(new int[]{i, j});
                    grid[i][j] = 0;
                    while (!stack.isEmpty()) {
                        int[] cur = stack.pollFirst();
                        curArea++;
                        for (int[] direct : direction) {
                            int row = cur[0] + direct[0];
                            int column = cur[1] + direct[1];
                            //找出相邻的所有岛屿
                            if (row > -1 && column > -1 && row < rows && column < columns && grid[row][column] == 1) {
                                stack.addFirst(new int[]{row, column});
                                //走过的地方不能再走
                                grid[row][column] = 0;
                            }
                        }
                    }
                    area = Math.max(area, curArea);
                }
            }
        }
        return area;
    }

    /**
     * 广度优先搜索+链表
     *
     * @param grid
     * @return
     */
    public static int BFSmaxAreaOfIsland(int[][] grid) {
        //面积
        int area = 0;
        //定义四个方向
        int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int rows = grid.length;
        int columns = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                //遍历找到一个岛屿
                if (grid[i][j] == 1) {
                    int curArea = 0;
                    //搜索这个岛屿相邻的岛屿个数
                    Deque<int[]> deque = new ArrayDeque<>();
                    deque.addLast(new int[]{i, j});
                    grid[i][j] = 0;
                    while (!deque.isEmpty()) {
                        int size = deque.size();
                        curArea += size;
                        //取出上一层元素
                        while (size-- > 0) {
                            int[] cur = deque.pollFirst();
                            for (int[] direct : direction) {
                                int row = cur[0] + direct[0];
                                int column = cur[1] + direct[1];
                                //找出相邻的所有岛屿
                                if (row > -1 && column > -1 && row < rows && column < columns && grid[row][column] == 1) {
                                    deque.addLast(new int[]{row, column});
                                    //走过的地方不能再走
                                    grid[row][column] = 0;
                                }
                            }
                        }
                    }
                    area = Math.max(area, curArea);
                }
            }
        }
        return area;
    }

}
